\section{选数(P1036)}

\subsection{题目描述}

已知 n 个整数 x1,x2,…,xn，
以及1个整数k(k<n)。从n个整数中任选kkk个整数相加，可分别得到一系列的和。
例如当n=4,k=3,4个整数分别为3,7,12,19时，可得全部的组合与它们的和为：

3+7+12=22

3+7+19=29

7+12+19=38

3+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=29。

\subsection{输入}
键盘输入，格式为：

n,k(1≤n≤20,k<n1)

x1,x2,…,xn(1≤xi≤5000000)

\subsection{输出}
屏幕输出，格式为： 111个整数（满足条件的种数）。

\subsection{样例}
\textbf{输入样例}
\begin{lstlisting}
4 3
3 7 12 19
\end{lstlisting}
\textbf{输出样例}
\begin{lstlisting}
1
\end{lstlisting}

%\subsection{提示}

\subsection{分析}
本题相对简单，难点有两个：（1）用dfs把所有可能的和存储起来；（2）用筛选法求1到最大和的所有质数；
这两个困难克服了之后，把重复的过滤掉，然后数一数是质数的那些和的个数。

\subsection{代码}
\begin{lstlisting}
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std; 
typedef long long ll; 

#define N 21
#define BN (20*5000000/32 + 1)

vector<ll> all_sum; 
vector<ll> deduped_sum; 

unsigned bitmap[BN]; 


ll max_sum; 
int a[N]; 
int n, k; 

int visited[N]; 

void dfs(int l, int s, ll sum)
{
	if (l==k) {
		max_sum = max(max_sum, sum); 
		all_sum.push_back(sum); 
		return; 
	}
	for (int i=s; i<n; i++) {
		if (visited[i])
			continue; 
		visited[i] = 1; 
		dfs(l+1, i, sum+a[i]); 
		visited[i] = 0; 
	}
}

int count(void)
{
	int ret = 0;
	ll sqrt_max_sum = (ll)sqrt(max_sum) + 1; 
	for (ll i=2; i<=sqrt_max_sum; i++) {
		ll a=i/32, b=a%32; 
		if ((bitmap[a]&(1<<b))!=0) {
			continue; 
		}
		for (ll j=2*i; j<=max_sum; j+=i) {
			ll a=j/32, b=j%32; 
			bitmap[a] |= (1<<b); 
		}
	}
	sort(all_sum.begin(), all_sum.end()); 
	ll last=-1; 
	for (unsigned i=0; i<all_sum.size(); i++) {
		if (all_sum[i]==last)
			continue; 
		deduped_sum.push_back(all_sum[i]); 
		last = all_sum[i]; 
	}

	for (unsigned i=0; i<all_sum.size(); i++) {
		ll j = all_sum[i]; 
		ll a=j/32, b=j%32; 
		if ((bitmap[a] & (1<<b))==0) {
			ret ++; 
		}
	}
	return ret; 
}

int main()
{
	int res; 
	
	cin>>n>>k; 
	for (int i=0; i<n; i++) {
		cin>>a[i]; 
	}
	dfs(0, 0, 0); 
	
	res = count(); 
	cout<<res; 
	
	return 0; 
}
\end{lstlisting}


